package com.binarytree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution13 {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new LinkedList<>();
        if (root==null) return res;
        List<Integer> path = new ArrayList<>();
        getPath(root, res,path);
        return res;
    }

    public void getPath(TreeNode root, List<String> res,List<Integer> path) {
        path.add(root.val);
        if (root.left == null && root.right == null) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < path.size()-1; i++) {
                sb.append(path.get(i)).append("->");
            }
            sb.append(root.val);
            res.add(sb.toString());
            return;
        }
        if (root.left!=null) {
            getPath(root.left,res,path);
            path.remove(path.size()-1);
        }
        if (root.right!=null) {
            getPath(root.right,res,path);
            path.remove(path.size()-1);
        }
    }
}
